#include <bits/stdc++.h>
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

char ibuf[1<<24],*iptr=ibuf;
inline static int read(){
    int sum=0,ch=*iptr++;
    while(!isdigit(ch)) ch=*iptr++;
    while(isdigit(ch)) sum=sum*10+(ch^48),ch=*iptr++;
    return sum;
}

int n,m,cnt[500005];
uint val[500005],pre[500005];
struct{int x,y,z,t;}a[500005],b[500005];
struct Dat{
    int p,q,c,t,z;
    operator uint()const{
        return t*((uint)(m-c)*(m-p)-(p<q?val[q]-val[p]-(uint)c*(q-p):0));
    }
}c[500005];
signed main(){
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    fread(ibuf,1,1<<24,stdin),m=read(),n=read(); uint ans=0;
    for(int i=1,x,y,z;i<=n;val[x]=max((int)val[x],y),i++) x=read(),y=read(),z=read(),a[i]={x,y,z,read()},cnt[a[i].z]++;
    for(int i=m;i;i--) val[i]=max(val[i],val[i+1]); for(int i=1;i<=m;i++) val[i]+=val[i-1];
    for(int i=m;i;i--) cnt[i]+=cnt[i+1]; for(int i=1;i<=n;i++) b[cnt[a[i].z]--]=a[i]; *pre=ans+=*c={0,m,0,m-b[1].z,b[1].z};
    for(int i=1,p=0,q=m,M=0;i<=n;pre[i]=ans+=c[i]={p,q,M,b[i].z-b[i+1].z,b[i+1].z},i++){
        p=max(p,b[i].x),M=max(M,b[i].y); while(q && val[q]-val[q-1]<=M) q--;
    } memset(cnt+1,0,4*m);
    for(int i=1;i<=n;i++) cnt[b[i].t]++; for(int i=m;i;i--) cnt[i]+=cnt[i+1];
    for(int i=1;i<=n;i++) a[cnt[b[i].t]--]=b[i]; ans*=(m-a[1].t),c->p=c->q=-1;
    // for(int i=1;i<=n;i++) debug("%d %d %d %d\n",a[i].x,a[i].y,a[i].z,a[i].t);
    // ptr: 最后一个满足 p<q 的位置， lim: 最后一个没被填满的位置。拆贡献拆吐了
    for(int i=1,p=0,q=m,M=0,p1=1,p2=1,lim=m,ptr=m;i<=n;i++){
        p=max(p,a[i].x),M=max(M,a[i].y); while(c[lim].z<a[i].z) lim--;
        while(q && val[q]-val[q-1]<=M) q--; ptr=min(ptr,lim);
        while(p1<=lim && c[p1].p<p) c[p1++].p=-1; p1=min(p1,lim+1);
        while(p2<=lim && c[p2].c<M) c[p2++].q=-1; p2=min(p2,lim+1);
        while(~ptr && (ptr<p1?c[ptr].p:p)>=(ptr<p2?c[ptr].q:q)) ptr--;
        uint sum=pre[lim]-pre[max(p1,p2)-1]+Dat{p,q,M,m-c[min(p1,p2)-1].z};
        
        if(p1<p2) for(int i=p1;i<p2;i++) c[i].q=q,c[i].c=M,sum+=c[i];
        if(p2<p1) for(int i=p2;i<p1;i++) c[i].p=p,sum+=c[i];
        
        ans+=sum*(a[i].t-a[i+1].t);
    } printf("%u\n",ans);
}